package lib

import (
	"strconv"
)

func init() {
	Probs = append(Probs, Problem{
		Num:         60,
		Discription: "n!种排列组合的第k个组合",
		Level:       3,
		Labels: map[string]int{
			"数学": 1,
		},
	})
}

// GetPermutation 跟通过回溯求所有排列组合反着来
//
//	@param n
//	@param k
//	@return string
func GetPermutation(n int, k int) string {
	//combs[i]表示i个数字能形成的排列个数
	combs := make([]int, n)
	combs[0] = 1
	for i := 1; i < n; i++ {
		combs[i] = combs[i-1] * i
	}

	//备选的数字
	nums := make([]int, n)
	for i := 0; i < n; i++ {
		nums[i] = i + 1
	}

	//从最高位开始，查看当前位数时的排列组合是否满足k
	//满足的话直接给下一位（index=0）
	//不满足的话，把剩下的排列组合个数传给下一位（k / combs[i]，k -= combs[i] * index）
	str := ""
	k--
	for i := n - 1; i >= 0; i-- {
		index := k / combs[i]
		str += strconv.Itoa(nums[index])
		nums = append(nums[:index], nums[index+1:]...)
		k -= combs[i] * index
	}

	return str
}
